//请实现两个函数，分别用来序列化和反序列化二叉树。 
//
// 示例: 
//
// 你可以将以下二叉树：
//
//    1
//   / \
//  2   3
//     / \
//    4   5
//
//序列化为 "[1,2,3,null,null,4,5]" 
//
// 注意：本题与主站 297 题相同：https://leetcode-cn.com/problems/serialize-and-deserialize-b
//inary-tree/ 
// Related Topics 树 设计 
// 👍 93 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

//Java：序列化二叉树
public class XuLieHuaErChaShuLcof{
    public static void main(String[] args) {
//        Solution solution = new XuLieHuaErChaShuLcof().new Solution();
        
    }
    class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    //层序遍历
    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if ( root == null ){
            return "[]";
        }
        StringBuilder answer = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){{ add(root); }};
        while( !queue.isEmpty() ){
            TreeNode node = queue.poll();
            if ( node != null ){
                answer.append( node.val +"," );
                queue.add( node.left );
                queue.add( node.right );
            }
            else {
                answer.append( "null," );
            }
        }
        //把最后一个","去掉
        answer.deleteCharAt( answer.length() -1 );
        answer.append("]");
        return answer.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if( "[]".equals( data ) ){
            return null;
        }
        //头和尾的"[]"都不包括在内
        String[] values = data.substring(1,data.length() - 1 ).split(",");
        //第一个元素
        TreeNode root = new TreeNode( Integer.parseInt( values[0] ) );
        Queue<TreeNode> queue = new LinkedList<TreeNode>(){{ add(root); }};
        //当前遍历到的数组元素下标
        int i = 1;
        while ( ! queue.isEmpty() ){
            //拿出队列的头节点，然后删除掉头节点
            TreeNode node = queue.poll();
            //左子树开始构建
            if( ! values[i].equals("null") ){
                node.left = new TreeNode( Integer.parseInt( values[i] ) );
                queue.add( node.left );
            }
            i++;
            //轮到右子树
            if ( ! values[i].equals("null") ){
                node.right = new TreeNode( Integer.parseInt( values[i] ) );
                queue.add( node.right );
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
//leetcode submit region end(Prohibit modification and deletion)

}
